\chapter{Algorithme optimal pour les graphes bipartits}
\section{Présentation de l'algorithme}
\subsection{Introduction}
Nous avons pris comme algorithme optimal celui des graphes de flux. Nous avons donc créé un type de graphe, prenant un graphe biparti et sa couverture par couleur en paramètre et nous retournant le graphe de flux associé.
Cet algorithme consiste à trouver successivement des chemins entre les sommets S et T et à les marquer. Lorsqu'il n'y a plus de chemins disponibles, alors on récupère la couverture minimale en prennant les sommets du chemin en cours pouvant accéder à T, et ceux ne faisant pas partie du chemin dont S est le père.
\subsection{Algorithmes}
Soit F et N des files.
\begin{algorithmic}
\STATE $trouver\_chemin(S,T):$
\STATE $F \gets \emptyset$
\STATE $N \gets \emptyset$
\FORALL{$v \in Adj(S)$}
\STATE $F.push((S,v))$
\ENDFOR
\WHILE{$F.empty() = false$}
\STATE $(x,u) \gets F.pop()$
\STATE $N.push(u)$
\IF{$|Adj(u)| = 0$}
\RETURN $N$
\ENDIF
\FORALL{$v \in Adj(u)$}
\IF{$v = T$}
\STATE $Adj(S) \gets Adj(S)-x$
\STATE $Adj(x) \gets Adj(x)-u$
\STATE $Adj(u) \gets Adj(u)-T+x$
\RETURN $trouver\_chemin(S,T)$
\ELSE
\STATE $F.push((u,v))$
\ENDIF
\ENDFOR
\ENDWHILE
\RETURN $N$
\end{algorithmic}
\subsection{Commentaires}
A la fin de l'execution de l'algorithme, celui ci retourne N qui contient le chemin en cours.
\section{Estimation de la complexité}
Soit G le graphe instance du probleme VC, G = (V,E), n = |V|, m = |E|.\\
La complexité de la transformation d'un graphe en graphe de flux est $O(n^{2})$.
La complexité de notre algorithme $trouver\_chemin$ est $O(n^{2})$. On a au plus $n/2$ appels recursifs \`a $trouver\_chemin$ et on parcourt au plus $2n$ sommets du graphe \`a chaque appel car quelque soit l'appel, le graphe de flux est un ensemble d'arbres o\`u chaque sommet du graphe apparait au plus une fois, donc le parcours du graphe de flux correspond à un parcours en profondeur sur l'arbre dont la racine est le sommet S.
La complexité de la transformation du chemin N en couverture du graphe est $O(n)$.\\
La complexité de l'algorithme optimal pour les graphes bipartits et $O(n^{2})$
\section{Résultats d'expérimentation}

On peut donc vérifier expérimentalement que notre algorithme a une complexité en $O(n^{2})$ .
\begin{center}
\input{../VertexCover/src/results/graph3}
\end{center}